package structure.array;

public class LeetCode_912 {

    public static void main(String[] args) {

        int[] ints = {5, 2, 3, 1};
        int[] ints1 = sortArray(ints);
        for (int i : ints1) {
            System.out.print(i + "\t");
        }

    }

    public static int[] sortArray(int[] nums) {
        if (nums.length == 1) {
            return nums;
        }
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

    private static void merge(int[] nums, int left, int mid, int right) {
        int[] res = new int[right - left + 1];

        int index = 0, leftIndex = left, rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (nums[leftIndex] <= nums[rightIndex]) {
                res[index++] = nums[leftIndex++];
            } else {
                res[index++] = nums[rightIndex++];
            }
        }
        while (leftIndex <= mid) {
            res[index++] = nums[leftIndex++];
        }
        while (rightIndex <= right) {
            res[index++] = nums[rightIndex++];
        }
        for (int i = 0; i < index; i++) {
            nums[i + left] = res[i];
        }
    }


}
